1. Field of the Invention
The invention generally relates to a cell switch for use in an asynchronous transfer mode (ATM) network; and in particular, to a cell switch supporting multicast connections and providing connection failure detection and handling in an ATM network.
2. Background of the Invention
Asynchronous transfer mode (ATM) is a cell relay data transmission technique selected as the transport scheme for the B-ISDN (Broadband Integrated Services Digital Network) standard. ATM Communication networks have applications in high speed digital communication carried in such media as synchronous optical networks. An ATM network transmits data of all types (e.g., voice, data, and video) based on asynchronous time division multiplexing. The data are transmitted in the form of fixed-length data packets, called xe2x80x9cATM cells.xe2x80x9d An ATM cell is 53 bytes long, of which 5 bytes are the cell header and 48 bytes are the cell payload. The cell header carries information used for identification and routing. Traffic within an ATM network is routed through connection nodes within the network where the connection nodes are in turns connected via one or more. ATM switches. An ATM switch in an ATM network is primarily responsible for routing the cells to their respective destinations.
An ATM network uses the concepts of xe2x80x9cvirtual pathsxe2x80x9d (VP) and xe2x80x9cvirtual channelsxe2x80x9d (VC) to allow routing of ATM cells between adjacent connection nodes. Therefore, the cell header of an ATM cell does not specify the full destination address. Rather, the cell header includes, among other things, an 8-bit virtual path identifier (VPI) and a 2-byte virtual channel identifier (VCI) (sometimes referred to as virtual connection identifier), identifying the virtual path and the virtual channel of the cell""s next switching stage. The VPI and VCI together identify the connection, called a virtual connection (VC), to which an ATM cell belongs. The cell header of an ATM cell is updated at each switching stage to include the VPI and VCI values of the next switching stage.
Communications in an ATM network can take the form of unicast or multicast. In unicast communication, ATM cells from a sender are transmitted to one recipient only. On the other hand, multicast refers to a xe2x80x9cpoint-to-multipoint connection.xe2x80x9d In multicast data communication, a sender sends the same ATM cells simultaneously to several recipients within the network. Broadcast is the extreme case of multicast where every user on the network receives the data transmitted by the sender. Recently, there is an increasing demand for multicasting in ATM networks and efficient implementations of multicasting are, therefore, desired.
FIG. 1 illustrates a multicast communication in an ATM network. In FIG. 1, a computer, denoted PC 22, communicates with other computers, PCs 12-16, through an ATM network 10 including ATM switches 24-27. PC 22 intends to send the same data traffic to recipient PCs 12-16. If ATM network 10 does not support multicasting, PC 22 has to replicate the data for each recipient and send the data separately to each of recipient PCs 12-16. This method becomes very inefficient when the number of recipients is large. In ATM network 10 which supports multicasting, PC 22 sends data traffic to multiple recipients (PCs 12-16) without having to transmit the data more than once. ATM switches 24-27 are responsible for directing the data traffic received from PC 22 to all of the intended recipients in network 10.
A conventional implementation of multicasting in an ATM network involves replicating the cells within the network and assigning the correct VPI/VCI values for each cell for routing to the multiple recipients. For example, in ATM network 10, PCs 12-16, belonging to the same multicast group for receiving multicast data traffic from PC 22, are put on a multicast list. ATM network 10 establishes the necessary connections according to the multicast list. When PC 22 sends multicast ATM cells to switch 24, switch 24 replicates the cells and sends the cells to the destination switches according to the multicast list. Here, switch 24 sends replicated multicast ATM cells to switches 25, 26 and 27. Switch 25 in turn replicates the ATM cells and sends the cells to PCs 12 and 13. Similarly, switch 27 replicates and transmits the multicast ATM cells to PCs 15 and 16. Meanwhile, switch 26 transmits the ATM cells to PC 14 without any replication since switch 26 only needs to service one recipient.
A conventional ATM switch used to connect a number of connection nodes within an ATM network is illustrated in FIG. 2. ATM switch 30 includes input ports 31a-c, switching elements 32a-c, and output ports 33a-c. The input ports, the switching elements, and the output ports are interconnected to form switch fabric which enables an ATM cell at any input port to be routed to any specified output port. ATM switch 30 further includes a controller 38 for controlling the operation of the switch, including setting up the input and output ports (through buses 35 and 37) and managing all of the switch traffic moving through switch fabric 34 (through bus 36).
To implement multicasting in ATM switch 30, multicast cells received at any of input ports 31a-c are replicated by switching elements 32a-c and then provided to the respective output ports 33a-c for transmitting to the next switching stage. Thus, switching elements 32a-c must include a sufficiently large memory for storing all of the replicated multicast cells.
Although implementation of multicasting based on cell replication provides flexibility, the implementation has several disadvantages. First, replication requires a large amount of redundant cell memory space in each of the ATM switches to store the replicated cells. The large memory requirement results in a large hardware implementation. Second, besides a large memory requirement, replication requires a large bandwidth to handle the large numbers of replicated cells. Furthermore, the input process could be on-hold until the replication at the output process is completed. In such case, implementation of multicast by replication tends to result in an inefficient use of resources.
To avoid cell replication in multicast connections, an ATM switch can be implemented using a central memory topology as illustrated in FIG. 3. In ATM switch 42 of FIG. 3, ATM cells received on input ports 44a-h are stored in a main cell memory 45. A controller 43 in ATM switch 42 is responsible for commanding the storage of incoming ATM cells and managing the data flow through switch 42. To transmit ATM cells, controller 43 accesses the memory locations where the ATM cells are stored and provides a copy of the cell to a buffer associated with the selected one of output ports 46a-h. Controller 43 is also responsible for updating the cell header information for the outgoing ATM cell. Output ports 46a-h transmit the ATM cells in their respective buffers together with the updated cell header values.
To establish multicast communications, the output ports desiring to receive multicast communications from a certain input port are put on a multicast list maintained by controller 43. To transmit a multicast cell to a number of output ports 46a-h, controller 43 accesses the stored multicast cell multiple times for each output port on the multicast list. Controller 43 modifies the header information (such as VPI/VCI values) of the multicast cell for each destination output port. In this manner, multicasting in an ATM switch employing a central memory topology can be implemented without replication of the multicast ATM cells. However, the above-described implementation of multicasting is often complex and therefore, places severe constraints on the multicasting capability of the ATM switch.
FIG. 4 illustrates another implementation of multicasting in ATM switch 42 of FIG. 3. In this implementation, controller 43 of ATM switch 42 maintains a connection memory 100 containing entries which define the connectivity between the input ports 44a-h and the output ports 46a-h in switch 42. Essentially, each entry in connection memory 100 defines a particular connection or virtual connection (VC) handled by the ATM switch. In FIG. 4, each entry in connection memory 100 includes a destination VPI (DVPI) field 112, a destination VCI (DVCI) field 114, and an output port number field 116. Each entry in connection memory 100 further includes a head field 117, a tail field 118, and a count field 119, which are used for managing the cell queue for each connection. Controller 43 maintains a cell queue table for each VC in connection memory 100. A cell queue table includes the address locations of all of the ATM cells stored in main cell memory 45 destined for a specific connection. The head field 117 for a VC entry is a pointer pointing to the first item in the cell queue table of that VC entry. The tail field 118 is a pointer pointing to the last item in the cell queue table for that VC entry and the count field 119 contains the number of ATM cells outstanding in the cell queue table.
In connection memory 100, output port number field 116 is used to indicate the output port for the particular VC entry. In the present example, switch 42 has eight output ports and thus output port number field 116 has 8 bits where each bit represents one output port. An output port is selected by a VC entry by setting the associated output port bit to xe2x80x9c1xe2x80x9d while the remaining bits are set to xe2x80x9c0.xe2x80x9d For example, entry 101 in connection memory 100 is destined for output port 4 since bit 4 of output port number field is set to xe2x80x9c1.xe2x80x9d
To implement multicasting in switch 42, controller 43 allocates one entry in connection memory 100 as a multicast master entry, denoted as entry 102 in FIG. 4. Controller 43 further allocates a consecutive block of memory locations in connection memory 100 for storing virtual connection entries for each multicast member. Because switch 42 has only eight output ports, only eight member entries need to be allocated. In FIG. 4, entries 103 to 110 are the memory locations allocated for up to eight multicast members in the multicast group. In master entry 102, the 8-bit field of output port number field 116 is used to identify the members of the multicast group. For example, in FIG. 4, member entries number 0-4 and 7, corresponding to output ports 0-4 and 7 are identified as belonging to the multicast group of master entry 102. The controller 43 sets up the DVPI field, the DVCI field, and the output port number for each of the member entries 103-110.
When a multicast ATM cell is received, multicast master entry 102 causes the ATM cell to be sent to the member entries identified by output port number field 116. Thus, the same ATM cell is sent to a number of output ports without the need for replication because the same cell stored in main cell memory 45 is sent to the designated output ports in turn. After a multicast cell is transmitted to all of the intended recipient output ports, the cell is removed from the cell queue table of master entry 102 and also from main cell memory 45.
Although the multicast implementation in FIG. 4 achieves efficient cell memory usage by eliminating cell replication, the multicast implementation has several disadvantages. First, the multicast implementation of FIG. 4 limits the number of multicast recipients to one recipient per output port. However, it is often desirable to be able to transmit more than one multicast cell to multiple recipients, destined for different subsequent switching stages, on the same output port. Second, the above described implementation is only capable of supporting a limited number of output ports or multicast members. If the number of multicast members desiring multicasting is large, then the output port number field needs to be expanded and the number of memory allocations for member entries also needs to be expanded. The implementation becomes inefficient when the allocated memory block becomes too large.
Therefore, it is desirable to provide a multicast implementation in an ATM switch which can transmit ATM cells to any number of output ports and to any number of connections at each output port. Furthermore, it is desirable to provide an ATM switch with connection failure detection and recovery scheme such that data transmission in an ATM network is not adversely affected by a malfunctioning output port.
According to the present invention, an ATM switch for transmitting a multicast ATM cell includes a memory, a control circuit and a cell memory. The control circuit maintains in the memory a connection table which includes a multicast master entry and one or more multicast member entries associated with the multicast master entry. The cell memory stores one or more ATM cells, including the multicast ATM cell. The multicast master entry holds an address of the cell memory at which the multicast ATM cell is stored. The multicast member entries are linked to each other through a circular double linked list.
In one embodiment, the multicast master entry includes a first pointer pointing to the circular double linked list of multicast members entries.
According to another embodiment of the present invention, each of the multicast member entries has a third pointer and a fourth pointer for forming the circular double linked list. Each of the third pointers of the multicast member entries point to the next member entry, thereby connecting the multicast member entries in a forward direction. Each of the fourth pointers of the multicast member entries point to the previous member entry, thereby connecting the multicast member entries in a reverse direction.
Besides being able to support multicasting without the need to replicate multicast cells, the multicast implementation of the present invention permits transmitting multicast connections to more than one multicast recipient per output port. Also, the multicast implementation does not limit the number of multicast member entries for each multicast group and thus can support a multicast group with a large number of members. Lastly, the multicast implementation of the present invention requires fewer logic elements to implement than conventional multicast implementations and allows for flexibility and efficient use of memory space.
The present invention is better understood upon consideration of the detailed description below and the accompanying drawings.